﻿//1802. 有界数组中指定下标处的最大值
//给你三个正整数 n、index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums（下标 从 0 开始 计数）：
//nums.length == n
//nums[i] 是 正整数 ，其中 0 <= i < n
//abs(nums[i] - nums[i + 1]) <= 1 ，其中 0 <= i < n - 1
//nums 中所有元素之和不超过 maxSum
//nums[index] 的值被 最大化
//返回你所构造的数组中的 nums[index] 。
//注意：abs(x) 等于 x 的前提是 x >= 0 ；否则，abs(x) 等于 - x 。


class Solution {
public:
    bool valid(int mid, int n, int index, int maxSum)
    {
        int left = index;
        int right = n - index - 1;
        return mid + cal(mid, left) + cal(mid, right) <= maxSum;
    }

    long cal(int big, int length)
    {
        if (length + 1 < big) {
            int small = big - length;
            return (long)(big - 1 + small) * length / 2;
        }
        else {
            int ones = length - (big - 1);
            return (long)big * (big - 1) / 2 + ones;
        }
    }

    int maxValue(int n, int index, int maxSum)
    {
        int left = 1, right = maxSum;
        while (left <= right)
        {
            int mid = (left + right + 1) / 2;
            if (valid(mid, n, index, maxSum))
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        return left - 1;
    }
};